import heapq
from typing import List


class Solution:
    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:
        n = len(times)

        times = [[s, e, i] for i, (s, e) in enumerate(times)]
        times.sort()

        chairs = list(range(n))
        leave = []

        for s1, e1, i in times:
            # 处理已经离开的人
            while leave and leave[0][0] <= s1:
                e, chair = heapq.heappop(leave)
                heapq.heappush(chairs, chair)

            # 选择当前最靠前的椅子
            chair = heapq.heappop(chairs)
            heapq.heappush(leave, [e1, chair])

            # 如果当前为目标人物
            if i == targetFriend:
                return chair

            # print((s1, e1, i), chairs, leave)


if __name__ == "__main__":
    print(Solution().smallestChair(times=[[1, 4], [2, 3], [4, 6]], targetFriend=1))  # 1
    print(Solution().smallestChair(times=[[3, 10], [1, 5], [2, 6]], targetFriend=0))  # 2

    # 测试用例45/60
    # 2
    print(Solution().smallestChair(times=
                                   [[33889, 98676], [80071, 89737], [44118, 52565], [52992, 84310], [78492, 88209],
                                    [21695, 67063], [84622, 95452], [98048, 98856], [98411, 99433], [55333, 56548],
                                    [65375, 88566], [55011, 62821], [48548, 48656], [87396, 94825], [55273, 81868],
                                    [75629, 91467]], targetFriend=6))
